package com.heima.leetcode.datastructure.linkedlist;

import com.sun.source.tree.BreakTree;

/**
 * <h2>判断链表是否有环 141</h2>
 * <h2>检测环的入口 142</h2>
 */
public class HasCycle {

    /**
     * <h3>判断链表是否有环</h3>
     * <strong>龟兔赛跑法</strong><br><br>
     * <strong>阶段一</strong>
     * <ol>
     * <ul>
     *     <li>龟一次走一步，兔子一次走两步</li><br>
     *     <li>当兔子能到达终点时，不存在环</li><br>
     *     <li>当兔子能追上龟时，存在环</li><br>
     * </ul>
     * </ol>
     * <strong>阶段二</strong>
     * <ol>
     * <ul>
     *     <li>从他们第一次相遇开始，龟回到起点，兔子保持原位不变</li><br>
     *     <li>龟和兔子每次都走一步</li><br>
     *     <li>当再次相遇时就是环的入口</li><br>
     * </ul>
     * </ol>
     *
     * <strong>原理：</strong><br>
     * &nbsp&nbsp&nbsp&nbsp如果有环，则记起点到入口长a，一圈有c个节点，k为第一次相遇时离入口的长度
     * 当龟和兔第一次相遇时，龟走了a + n * c + k多个节点，兔走了a + m * c + k个节点
     * 相减 => (m - n) * c，又兔的速度是龟的两倍，所以(m - n) * c是龟走的距离，也就是
     * 说龟走的距离是圈长度的整数倍，又 a + n * c为圈的入口，故兔保持原地按照龟的速度
     * 再走a个节点就到了圈的入口，龟放到起点再走a个节点也到了圈的入口，也就会在入口处相遇。
     * <br><br>
     * @param head 链表头节点
     * @return 是否有环
     */
    public static boolean hasCycle(ListNode head) {
        ListNode rabbit = head;
        ListNode tortoise = head;
        while (rabbit != null && rabbit.next != null){
            rabbit = rabbit.next.next;
            tortoise = tortoise.next;
            if (rabbit == tortoise){
                return true;
            }
        }
        return false;
    }

    /**
     * 找到环的入口节点，对应上述的阶段二
     * @param head 链表的头节点
     * @return 入口节点
     */
    public static ListNode detectCycle(ListNode head){
        ListNode rabbit = head;
        ListNode tortoise = head;
        while (rabbit != null && rabbit.next != null){
            rabbit = rabbit.next.next;
            tortoise = tortoise.next;
            if (tortoise == rabbit){
                tortoise = head;
                while (true){
                    // 因为a为0的时候，就是一个环，第一次相遇龟走一圈，兔走两圈，相遇就是在入口，如果先移动再判断，则得出来的结果是第二个节点，所以，要先判断再移动
                    if (tortoise == rabbit){
                        return tortoise;
                    }
                    tortoise = tortoise.next;
                    rabbit = rabbit.next;
                }
            }
        }
        return null;
    }
}
